'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-08-21 09:31:44
'''

'''
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.

tips:注意最小深度的定义，到叶子节点的深度。如果节点只有一个孩子节点，就不是叶子节点，这样的没有到叶子节点，不能只给个0.
'''

from tree_node import *

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        from sys import maxsize
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        l = self.minDepth(root.left) if root.left else maxsize
        r = self.minDepth(root.right) if root.right else maxsize
        # print(l, r, min(l, r))
        return min(l, r)+1



if __name__ == "__main__":
    solution = Solution()
    null = 'null'
    root = [3,9,20,null,null,15,7]
    for i,v in enumerate(root):
        root[i] = str(v)
    s = ','.join(root)
    # print(s)
    o_s = OfficialSerialize()
    root = o_s.deserialize(s)
    print(solution.minDepth(root))